class Solution
{
    int dx[4] = { 1,-1,0,0 };
    int dy[4] = { 0,0,1,-1 };
    int m, n, k;
    bool vis[101][101];
    int ret = 0;
public:
    int wardrobeFinishing(int _m, int _n, int _cnt)
    {
        m = _m;
        n = _n;
        k = _cnt;
        dfs(0, 0);
        return ret;
    }

    void dfs(int i, int j)
    {
        ret++;
        vis[i][j] = true;
        for (int a = 0; a < 4; a++)
        {
            int x = dx[a] + i, y = dy[a] + j;
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && check(x, y))
            {
                dfs(x, y);
            }
        }
    }
    bool check(int i, int j)
    {
        int tmp = 0;
        while (i)
        {
            tmp += i % 10;
            i /= 10;
        }
        while (j)
        {
            tmp += j % 10;
            j /= 10;
        }
        return tmp <= k;
    }
};